// @(#)root/roostats:$Id: BayesianNetworkConstruction.cxx 
// Author: Shruti Gupta        20/08/2012
//_________________________________________________

/*
BEGIN_HTML
<p>
This class uses An Algorithm for Bayesian Belief Network Construction from Data to construct a Bayesian Network of databases.The algorithm takes a database and an attributes ordering (i.e., the causal attributes of an attribute should appear earlier in the order) as input and constructs a belief network structure as output. The Algorithm has three phases of operation: Drafting, Thinning and Thickening to produce an exact network as close to the  actual network as possible. The major step is drafting, which adds BayesianNetworkConstructions to a set provided there is no open path between them. The present algorithm makes use of the concept of d-separation, such that, when conditional mutual information is smaller than a certain threshold value ε , we say that the respective nodes are d-separated by the condition-set C, and they are conditionally independent. An open path exists when the nodes are d-separated given empty set.
</p>

<p>
This algorithm also makes the following assumptions: (1) The database attributes have discrete values and
there are no missing values in all the records. (2) The volume of data is large enough for reliable CI tests. (3) The
ordering of the attributes is available before the network construction, i.e., a node’s parents nodes should appear
earlier in the order.

The present class effectively does the drafting part of the algorithm.
</p>
END_HTML
*/
//_________________________________________________


//---The class does not contain a separate header, for coherent reading. It will be implemented in the final class.//  
#include<iostream>
#include<fstream>
#include<string>
#include<vector> 
#include<stdio.h>
#include<math.h>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <ctime>

//ClassImp(RooStats::BayesianNetworkConstruction);

using std::vector;
using std::ifstream;
using std::string;
using std::cout;
using std::endl;
using std::string;



class BayesianNetworkConstruction
	{
		public:
			int rank;
			double v1_val;
			double v2_val;
			char v1_name;
			char v2_name;
			double I;
			bool lessthan_e;
			int dir;
			//static int E,R;
			//int openPath;
			int InEPos;
			int InRPos;
			string arc;
			typedef struct node {
				int nodes;
				char name;
					}node;
			std::vector<node> ReadNodes ();
			void set_value (int,double,double,double,bool,int,int,char,char,char,int);
		 	void parintpair (int,double,double,double,bool,int,int,char,char,char,int);
			void Create_BayesianNetworkConstructions();
			std::vector<double> getJoint();
			double getI(double,double,double);
			bool lessThan_e(double);
			//void setOpenPath(int);
			std::string getArc(char,char);
			void ePosDet(int);
			//int countNoOfBayesianNetworkConstructions(int);
			
	};
   
//Taking a specific case with 10 nodes, therefore n*(n-1)/2 = 45 pairs.

BayesianNetworkConstruction pair[45];
static int E,R;
//static int nodeCount;


void BayesianNetworkConstruction::set_value (int a,double b,double c,double d,bool e,int f,int g,char h,char i,char j,int l)
	{
  		rank = a;
  		v1_val = b;
		v2_val = c;
		I = d;
		lessthan_e = e;
		dir = f;
		InEPos = g;
		arc = h;
		v1_name = i;
		v2_name = j;
		InEPos = l;
		
	}

void BayesianNetworkConstruction::parintpair (int a,double b,double c,double d,bool e,int f,int g,char h,char i,char j,int k)
	{
		cout << "BayesianNetworkConstruction rank: " << a << endl;
		cout << "BayesianNetworkConstruction v1: " << b << endl;
		cout << "BayesianNetworkConstruction v2: " << c << endl;
		cout << "BayesianNetworkConstruction I: " << d << endl;
		cout << "BayesianNetworkConstruction lessthan_e: " << e << endl;
		cout << "BayesianNetworkConstruction dir: " << f << endl;
		cout << "BayesianNetworkConstruction InEPos: " << g << endl;
		cout << "BayesianNetworkConstruction arc: " << h << endl;
		cout << "BayesianNetworkConstruction v1_name: " << i << endl;
		cout << "BayesianNetworkConstruction v2_name: " << j << endl;
	}

//The following method reads the name and value of the nodes from the database : here, a file with 10 nodes. 
std::vector<BayesianNetworkConstruction::node> BayesianNetworkConstruction::ReadNodes ()
	{
		std::vector<node> node1;
		
		int i=0;
		
		ifstream myfile ("input.txt");
  			if (myfile.is_open())
  				{
    						while(myfile.good())
							{
      							node1.push_back(node());
							myfile >> node1[i].name;
							node1.push_back(node());
							myfile >> node1[i].nodes;
							i++;
							}
							 
    						
    				myfile.close();	
  				}
			

  		else cout << "Unable to open file"; 
		int j;
		
	return node1;
	}
//Creates pairs taking values of v1,v2(the two nodes), their mutual information(I), and their joint probability (Joint) from respective functions. Furthermore, it sorts the pairs with respect to the I value keeping the rank same for future use.Test value of nodes = 10; 

void BayesianNetworkConstruction::Create_BayesianNetworkConstructions ()
	{
		BayesianNetworkConstruction BayesianNetworkConstruction2;
		
 		int i,j;
		std::vector<node> node2;
		std::vector<double> Joint1;
		//int count=countNoOfBayesianNetworkConstructions(nodeCount);
		Joint1 = BayesianNetworkConstruction2.getJoint();
		node2 = BayesianNetworkConstruction2.ReadNodes();
		double Joint_temp;
		BayesianNetworkConstruction temp;
		int temp1;		
		int paircounter=0;
			for(i=0;i<10;i++)
				{
				//cout << "Test:" << i << endl;
				for(j=i+1;j<10;j++)
					{
						
						
						pair[paircounter].v1_name=node2[i].name;
						pair[paircounter].v1_val=node2[i].nodes;
						pair[paircounter].v2_name=node2[j].name;
						pair[paircounter].v2_val=node2[j].nodes;
						Joint_temp = Joint1[paircounter];
						pair[paircounter].I = BayesianNetworkConstruction2.getI(Joint_temp,pair[paircounter].v1_val,pair[paircounter].v2_val);
						pair[paircounter].lessthan_e = BayesianNetworkConstruction2.lessThan_e(pair[paircounter].I);
						pair[paircounter].rank = paircounter+1;
						
						
						
						paircounter++;
					}

//BayesianNetworkConstruction2.setOpenPath(paircounter);				
				}
//Sorting:
			for(i=0;i<paircounter;i++)
				for(j=i+1;j<paircounter;j++)	
					{
						if(pair[i].I>pair[j].I)
							{
								temp = pair[i];
								pair[i] = pair[j];	
								pair[j] = temp;
								temp1 = pair[i].rank;
								pair[i].rank = pair[j].rank;	
								pair[j].rank = temp1;
								
								
							}
												
					}
			BayesianNetworkConstruction2.ePosDet(paircounter);
			for(i=0;i<paircounter;i++)
				{
				cout << "BayesianNetworkConstructions   " << pair[i].v1_name;
				cout << pair[i].v2_name ;
				cout << "      "  << pair[i].I << endl;
				cout << "      "  << pair[i].rank << endl;
				}
			cout << "E =     " << E << endl;
			cout << "R =     " << R ; 
		
	}
int BayesianNetworkConstruction::countNoOfBayesianNetworkConstructions(int n)
	{
		int temp;
		temp = n*(n-1)/2;
		return(temp);
	}
   
//Method returns the joint density for each pair: for now random generation.  

std::vector<double> BayesianNetworkConstruction::getJoint()
	{
		int i;
		std::vector<double> Joint;
		srand(time(0));
		double val;
		for(i=0;i<45;i++)
		{
		 val = (double)rand()/(double)RAND_MAX;
		 Joint.push_back(val);
		 //cout << val << endl;
		}

		//void uniform(UInt_t dimension, Double_t* vector, TRandom* generator = randomGenerator())


		double temp;
		ifstream myfile2 ("input2.txt");
		 int i=0;	
			if(myfile2.is_open())
				{
						
    						
							while(myfile2.good())
							{      							
							myfile2 >> temp;
							Joint.push_back(temp);
							}
							
							 
    						
    				myfile2.close();	
  				}
		

  		else cout << "Unable to open file"; 
		return Joint;
	}
//The method returns the mutual information of two nodes.	
double BayesianNetworkConstruction::getI(double a,double b,double c)
	{
		
		double I1=log (c/(a*b));
		double I=c*I1;
		return(I);
	}

bool BayesianNetworkConstruction::lessThan_E(double CI)
	{
		double E=13;
		if(CI<E)
		return(0);
		else
		return(1);
	}
//Method checks if the mutual information is above a certain value.
bool BayesianNetworkConstruction::lessThan_e(double I)
	{
		double e=13;//appropriate value to be chosen. Here, random.
		if(I<e)
		return(0);
		else
		return(1);
	}
//The following method adds the arcs to set E if there are no open paths between given nodes, otherwise to set R for the later phases.
//InEPos value tells whether the arc is in set E and similarly, InRPos stores this information for set R.
void BayesianNetworkConstruction::ePosDet(int BayesianNetworkConstructioncount)
	{
		int i;
		BayesianNetworkConstruction BayesianNetworkConstruction2;
		E=E+2;
		pair[0].InEPos = 1;
		pair[0].arc = BayesianNetworkConstruction2.getArc(pair[0].v1_name,pair[0].v2_name);
		pair[1].InEPos = 1;
		pair[1].arc = BayesianNetworkConstruction2.getArc(pair[1].v1_name,pair[1].v2_name);
		for(i=2;i<BayesianNetworkConstructioncount;i++)
			{
				if(pair[i].lessthan_e == 0)
				{
				pair[i].InEPos = 1;
				pair[i].arc = BayesianNetworkConstruction2.getArc(pair[i].v1_name,pair[i].v2_name);
				E++;
				}
				else
				{
				pair[i].InRPos = 1;
				pair[i].arc = BayesianNetworkConstruction2.getArc(pair[i].v1_name,pair[i].v2_name);
				R++;
				}
			}
		for(i=0;i<BayesianNetworkConstructioncount;i++)
				{
				cout << "Arc" << pair[i].arc ;
				if(pair[i].InEPos == 1)
				cout << "    E"  << endl;
				if(pair[i].InRPos == 1)
				cout << "    R"  << endl;
				}
	}
//This method returns the arc to be stored in set E or R.
std::string BayesianNetworkConstruction::getArc(char a,char b)
	{
		string x = " ";
		x+= a;
		x+= b;
		x+= " ";
		return (x);	
	}
//d-separation
void BayesianNetworkConstruction::setOpenPath(int BayesianNetworkConstructioncount)
	{
		int temp,x,i,y=0;
		std::ofstream myfile3;
  		myfile3.open ("file3.txt");
			for(i=0;i<BayesianNetworkConstructioncount;i++)
			{
		 		if(i%3 == 0)
				x = 1;
				else
				x=0;
  			myfile3 << x;
			myfile3 << "\n";	
			
			}
  		myfile3.close();
		std::ifstream myfile4;
		myfile4.open ("file3.txt");
			while(myfile4.good())
				{
				myfile4 >> temp;
				pair[y].openPath = temp;
				cout << "Test: " << pair[y].openPath;
				y++;
				}
		
  		myfile4.close();
	}
int main ()
	{
 		BayesianNetworkConstruction BayesianNetworkConstruction1;
  		BayesianNetworkConstruction1.Create_BayesianNetworkConstructions();
		
		
		return 0;
}


/*This class needs to be extended further to complete the thickening and thinning phase of the algorithm. A method to find minimum block set between nodes needs to be constructed as per the following algorrithm:
Procedure find_block_set (current graph, node1, node2)
begin
find all the undirected paths between node1 and node2;
store the open paths in open_path_set, store the closed paths in closed_path_set;
do
while there are open paths which have only one node do
store the nodes of each such path in the block set;
remove all the blocked paths by these nodes from the open_path_set and closed_path_set;
from the closed_path_set, find paths opened by the nodes in block set and move them to
the open_path_set, shorten such paths by removing the nodes that are also in the block set;
end while
if there are open paths do
find a node which can block maximum number of the rest paths and put it in the block set;
remove all the blocked paths by the node from the open_path_set and the closed_path_set;
from the closed_path_set, find paths opened by this node and move them to
the open_path_set, shorten such paths by removing the nodes that are also in the block set;
end if
until there are no open path
end procedure.*/







  
  
